\chapter{Model społeczeństwa polskiego}\label{modelPolski}

\section{Gry przestrzenne}

Bardzo ciekawym uogólnieniem koncepcji przedstawionych w poprzednim rozdziale
są \emph{gry przestrzenne}.
Modelują one interakcje między graczami umieszczonymi w przestrzeni
reprezentowanej przez pewien \emph{graf} (nieskierowany, bez pętli i krawędzi
wielokrotnych --- patrz \ref{graf}).
W każdym wierzchołku takiego grafu umieszczamy gracza.
Krawędzie wyznaczają między którymi graczami zachodzi interakcja.
Przyjmujemy, że rywalizacja jest opisywana przez daną
\emph{symetryczną grę dwuosobową} $\gra{}$, która jest rozgrywana
niezależnie pomiędzy każdą parą sąsiednich wierzchołków.
Gracze akumulują zyski ze wszystkich gier uzyskując w ten sposób pewną łączną
wypłatę.

\paragraph{}

Poprzez analogię do pojęcia profilu w zwykłej grze (patrz
\ref{profil}) dla gry przestrzennej wprowadzimy pojęcie
\emph{profilu przestrzennego}.

\begin{df}\label{profilPrzestrzenny}
\emph{Profil przestrzenny} to funkcja $\phi \, : \, V \mapsto S$ ze zbioru
wierzchołków $V(G)$ w zbiór strategii $S$ reprezentująca wybór strategii przez
wszystkich graczy.
Zbiór wszystkich profili przestrzennych to $\mathcal{Q} = S^V$.
\end{df}

\paragraph{}\label{lacznaWyplata}

Każdy gracz otrzymuje łączną wypłatę zależną od wybranej przez siebie strategii
oraz od strategii swoich sąsiadów.
Podobnie jak w przypadku sytuacji statycznej, łączną wypłatę można zdefiniować
jako funkcję $U \, : \, \mathcal{Q} \times V \mapsto \mathbb{R}$.
Przez $U(\phi,v)$ rozumiemy łączną wypłatę gracza $v$ w profilu $\phi$.

\paragraph{}

W powyższych terminach definicja gry przestrzennej przedstawia się następująco.

\begin{df}\label{graPrzestrzenna}
\emph{Grą przestrzenną} nazywamy trójkę uporządkowaną
$\tuple{\gra{}, \, G, \, U}$, gdzie
\begin{itemize}
\item[] $\gra{}$ --- symetryczna gra dwuosobowa,
\item[] $G$ --- graf nieskierowany,
\item[] $U$ --- funkcja łącznej wypłaty.
\end{itemize}
\end{df}


\section{Model społeczeństwa polskiego}

Na początek rozważymy kanoniczny dylemat Więźnia (por. \ref{dylematWieznia})
na rzeczywistej sieci powiązań społecznych.
Dzięki uprzejmości
\emph{Interdyscyplinarnego Centrum Modelowania Matematycznego i Komputerowego}
(ICM) \cite{icm} otrzymaliśmy dostęp do opisu grafu społeczeństwa polskiego
używanego w projekcie RIVERS \cite{rivers}.
Model ten został stworzony na podstawie bardzo dokładnych danych statystycznych
zebranych przez Główny Urząd Statystyczny (GUS).

\subsection{Graf społeczeństwa}

Rozważana sieć społeczna (ang. \emph{social network}) obejmuje ponad $35,\!8$
miliona wierzchołków reprezentujących członków społeczeństwa polskiego.
Krawędzie grafu odzwierciedlają relację znajomości, która wyznaczona jest
poprzez przynależność graczy do różnych grup społecznych --- zakładamy,
że wszyscy członkowie grupy znają się nawzajem.
Grupy mogą zmieniać się w czasie (por. \ref{modelPolskiDynamikaGrafu}), a każdy
gracz może należeć naraz do wielu z nich.
Wyróżniamy kilka typów podstawowych grup społecznych, których zestawienie
przedstawiamy w poniższej tabeli.

\begin{center}
\begin{tabular}{p{5cm}|c}
rodzaj grupy & liczba grup stale funkcjonująca w sieci\\
\hline
gospodarstwo domowe & $13,\!3$ mln\\
szkoła & $28,\!6$ tys\\
jednostka edukacji wyższej & $462$\\
zakład pracy & $760,\!5$ tys\\
\end{tabular}
\end{center}

\noindent
W naszym modelu gospodarstwa domowe liczą zazwyczaj kilka osób z najbliższej
rodziny.
Szkoły zrzeszają dzieci i młodzież.
Są to najczęściej grupy kilkunasto- bądź kilkudziesięcioosobowe.
Mamy też kilkaset uczelni wyższych, które organizują społeczne życie studentów.
Pozostałe grupy to różne zakłady pracy.
Niektóre z nich są zaledwie kilkuosobowe, inne liczbą nawet setki czy tysiące
członków.

Poniższy wykres przedstawia rozkład stopni wierzchołków w sieci.
\begin{figure}[H]\label{rozkladStopniPolski}
\begin{center}
\includegraphics[scale=0.8]{rozkladStopni.pdf}
\end{center}
\caption{Rozkład stopni wierzchołków.}
\end{figure}

\subsection{Wypłaty graczy}

Istnieje wiele sposobów naliczania łącznej wypłaty (por. \ref{laczneWyplaty}).
Co więcej, różne definicje powodują zazwyczaj różne zachowania dynamiki modelu.
W tym przypadku przyjęliśmy jedną z najprostszych możliwości:
\[
U(\phi,v) \; = \; \sum_{w \in \mathcal{N}(v)} u(\phi(v), \phi(w))
\]
Wartość ta odpowiada sumie wypłat ze wszystkich gier w danej turze.

\subsection{Dynamika}

Zachowanie naszej gry przestrzennej w czasie modelujemy za pomocą
\emph{łańcucha Markowa} (patrz \ref{lancuchMarkowa}).
W tym przypadku zbiorem stanów jest zbiór wszystkich par postaci
$\tuple{\phi, G(V)}$, gdzie $\phi$ to pewien profil przestrzenny, a $G(V)$ to
graf o ustalonym zbiorze wierzchołków $V$ --- reprezentujących członków
społeczeństwa polskiego.

\subsubsection{Dynamika populacji}

Badamy dwa różne sposoby ewolucji populacji.

\paragraph{Kanoniczny proces Morana.}
Jest to bardzo popularne podejście, które wykorzystywali w swych pracach
między innymi Santos i Pacheco \cite{sp}.
Wyznaczenie stanu populacji w momencie $t+1$ na podstawie stanu z chwili $t$
przebiega tu w następujący sposób.
Do zmiany strategii wybieramy losowy podzbiór graczy $W_t \subset V$ stanowiący
stałą frakcję populacji $|W_t| = N \cdot \alpha$.
Następnie dla każdego $x \in W_t$ wykonujemy jedno z dwóch posunięć:
\begin{enumerate}
\item Mutujemy gracza $x$, czyli przypisujemy mu losową strategię ze zbioru
$S = \{C, D\}$.
\item Wybieramy losowego sąsiada $y \in \mathcal{N}_t(x)$ wierzchołka $x$ i z
prawdopodobieństwem
\[p_{x,y} = \max\left\{\frac{1}{T-S} \cdot \frac{U(\phi_t,y) - U(\phi_t,x)}{\max(deg(x), deg(y))},0\right\}\]
przypisujemy graczowi $x$ strategię gracza $y$.
\end{enumerate}
Pierwsze z posunięć wykonujemy z prawdopodobieństwem $\epsilon$, a drugie z
prawdopodobieństwem $1 - \epsilon$.
Wartości $\alpha$ oraz $\epsilon$ są stałymi parametrami modelu.

\bigskip

Zauważmy, że opisana wyżej dynamika jest w pewnym sensie niesprawiedliwa.
Może się zdarzyć, że stopnie wierzchołków $x$ i $y$ będą znacznie się różnić.
Niemniej jednak we wzorze na $p_{x,y}$ wypłaty obu wierzchołków są dzielone
przez $\max(deg(x), deg(y))$.
W rezultacie gracz o mniejszym stopniu traci na tym przeskalowaniu.
Z tego powodu rozpatrzyliśmy nieco zmodyfikowaną wersję powyższego podejścia.

\paragraph{Sprawiedliwy proces Morana.}

Ta dynamika populacji różni się od poprzedniej sposobem wyznaczania
prawdopodobieństwa $p_{x,y}$.
W tym przypadku przyjmujemy
\[p_{x,y} = \max\left\{\frac{1}{T - S} \cdot \left(\frac{U(\phi_t,y)}{deg(y)} - \frac{U(\phi_t,x)}{deg(x)}\right),0\right\}\]
Reszta pozostaje bez zmian.


\subsubsection{Dynamika grafu}\label{modelPolskiDynamikaGrafu}

Równolegle ze zmianami w populacji modyfikacjom poddajemy samą sieć.
W każdej turze wysyłamy pewną stałą frakcję $\beta$ członków społeczeństwa
w krótkie podróże, podczas których dochodzi do zawierania nowych znajomości.
W tym celu wprowadzamy do sieci nowe, tymczasowe grupy zwane
\emph{paczkami podróżnych}.
Mają one odzwierciedlać otoczenie podróżników, czyli na przykład przedział
w pociągu albo kilka najbliższych siedzeń w autobusie.
Przyjmujemy, że w skład pojedynczej paczki może wejść maksymalnie 10 osób.
W modelu projektu RIVERS zawarte są informacje o miejscu przebywania każdego
członka społeczeństwa (z dokładnością do 1 km$^2$).
Korzystamy z nich przy formowaniu paczek podróżnych.
Dzięki temu do jednej paczki trafiają zawsze gracze, którzy znajdują się
blisko siebie w przestrzeni i zmierzają w to samo miejsce.
Każdy gracz, wyruszając w podróż, zrywa na okres jej trwania połączenia z jego
stałymi grupami (domownikami, współpracownikami, itp).
Zostają one przywrócone dopiero po powrocie z wojaży.
Podróże mogą mieć różną długość (wyrażaną liczbą kroków symulacji), ale zawsze
się kończą.
W danej chwili gracz możne należeć tylko do jednej paczki podróżnych.
Niemniej jednak w ciągu jednej podróży grupy wolno zmieniać wielokrotnie.
W ten sposób opisujemy przesiadki i dynamicznie zmieniające się otoczenie
podróżnego.
Zmiana paczki przebiega analogicznie do rozpoczynania podróży.

Powyższy proces można opisać analogicznie do dynamiki populacji.
Nie będziemy tego jednak w tym miejscu czynić, gdyż dokładne wyjaśnienie
mechanizmu tworzenia podróżników i ich paczek oraz wytyczania tras wymagałoby
zagłębienia się w dość skomplikowaną strukturę modelu społeczeństwa
polskiego projektu RIVERS


\subsection{Symulacje}

Przeprowadziliśmy komputerowe symulacje opisanych wyżej wariantów dynamiki
modelu społeczeństwa polskiego.
W początkowym profilu przestrzennym zawsze przypisywaliśmy graczom strategie
ze zbioru $S = \{C, D\}$.
Każdy z nich z prawdopodobieństwem $\frac{1}{2}$ współpracował, a w przeciwnym
wypadku zdradzał.
W ramach jednej symulacji wykonywaliśmy najpierw $A = 2000$ kroków ewolucji
gry, aby stan systemu mógł przybliżyć się do rozkładu stacjonarnego.
Następnie przeprowadzaliśmy dodatkowe $B = 500$ kroków w celu zmierzenia
przybliżonych własności tego rozkładu.
Do zmiany strategii wybieraliśmy w każdej turze losową frakcję
$\alpha = 10^{-2}$ osobników.
Mutacja następowała z prawdopodobieństwem $\epsilon = 10^{-3}$.
Rozważyliśmy kilka różnych wartości parametru $\beta$, który oznacza odsetek
podróżujących w danej chwili graczy.

\subsubsection{Mierzone wartości}\label{mierzoneWartosci}

Mierzyliśmy średnią i odchylenie standardowe frakcji współpracujących graczy
oraz średnią frakcji graczy zmieniających strategie.
Poniżej przedstawiamy dokładne definicje.

\begin{df}\label{poziomKooperacji}
Przez $\rho_n$ oznaczamy \emph{poziom kooperacji} po $n$--tej turze, czyli
stosunek liczby graczy współpracujących do wszystkich graczy.

\medskip{}

\noindent
Przez $\hat{\rho}$ oznaczamy \emph{średni poziom kooperacji}, równy
\[ \hat{\rho} \; = \; \frac{1}{B} \sum_{n = A + 1}^{A + B} \rho_n \]

\medskip{}

\noindent
Przez $\tilde{\rho}$ oznaczamy \emph{odchylenie standardowe poziomu kooperacji},
równe
\[ \tilde{\rho} \; = \; \sqrt{\frac{1}{B} \sum_{n = A + 1}^{A + B} (\rho_n - \hat{\rho}})^2 \]
\end{df}

\begin{df}\label{poziomZmian}
Przez $\delta_n$ oznaczamy \emph{poziom zmian strategii} po $n$--tej turze,
czyli stosunek liczby graczy zmieniających strategię do wszystkich graczy.

\medskip{}

\noindent
Przez $\hat{\delta}$ oznaczamy \emph{średni poziom zmian strategii}, równy
\[ \hat{\delta} \; = \; \frac{1}{B} \sum_{n = A + 1}^{A + B} \delta_n \]
\end{df}

Oprócz tego mierzyliśmy także średni poziom kooperacji w grupach o danej
liczności.
Przez $\kappa(s)$ rozumiemy średnią ze wszystkich poziomów kooperacji w grupach
o liczności $s$ po ostatniej turze.

\subsubsection{Wyniki}

Nasze symulacje potwierdziły wyniki uzyskane przez Santosa i opisane w
\cite{sp}.
Okazuje się, że nie tylko matematyczne modele sieci społecznych, ale również ich
rzeczywiste odpowiedniki, charakteryzują się wysokim poziomem kooperacji.
Jest tak w przypadku obu rozważanych przez nas wariantów dynamiki.
\emph{Sprawiedliwy proces Morana} prowadzi jednak finalnie do nieco niższego
poziomu kooperacji niż podejście kanoniczne.
Na poniższych wykresach przestawione są poziomy kooperacji po kolejnych
turach symulacji i przy różnych wartościach parametru $\beta$.

\begin{center}
\begin{figure}[H]\label{poziomKooperacjiPolski}
\begin{tabular}{cc}
\includegraphics[scale=0.6]{kooperacyjnoscSym1.pdf}
&
\includegraphics[scale=0.6]{kooperacyjnoscSym2.pdf}
\end{tabular}
\caption{Poziom kooperacji po kolejnych turach symulacji.}
\end{figure}
\end{center}
Jak widać podróże wpływają na dynamikę w nieznacznym stopniu, ale zawsze
podnoszą poziom kooperacji o kilka procent.

\begin{center}
\begin{tabular}{m{5cm}|p{2cm}|p{2cm}|p{2cm}}
\textbf{Dynamika} & $\beta = 0,\!0$ & $\beta = 0,\!0005$ & $\beta = 0,\!0050$\\
\hline
\multirow{2}{*}{Kanoniczny proces Morana} &
$\hat{\rho} = 0,\!8252$ & $\hat{\rho} = 0,\!8262$ & $\hat{\rho} = 0,\!8350$\\
 & $\tilde{\rho} = 0,\!0023$ & $\tilde{\rho} = 0,\!0024$ & $\tilde{\rho} = 0,\!0032$\\
\hline
\multirow{2}{*}{Sprawiedliwy proces Morana} &
$\hat{\rho} = 0,\!8193$ & $\hat{\rho} = 0,\!8203$ & $\hat{\rho} = 0,\!8290$\\
 & $\tilde{\rho} = 0,\!0023$ & $\tilde{\rho} = 0,\!0023$ & $\tilde{\rho} = 0,\!0031$\\
\end{tabular}
\end{center}

Poziom zmian strategii przedstawia się następująco.

\begin{center}
\begin{figure}[H]\label{poziomZmianPolski}
\begin{tabular}{cc}
\includegraphics[scale=0.6]{zmianySym1.pdf}
&
\includegraphics[scale=0.6]{zmianySym2.pdf}
\end{tabular}
\caption{Poziom zmian strategii po kolejnych turach symulacji.}
\end{figure}
\end{center}
Obie dynamiki nie różnią się znacznie.
\emph{Sprawiedliwy proces Morana} charakteryzuje się jednak nieco wyższym
średnim poziomem zmian strategii.

\medskip{}

Najbardziej zaskakujący jest fakt, że kooperacja pojawia się częściej w grupach
o większej liczbie członków.
Obrazują to poniższe wykresy.
Czyżby zatem gospodarstwa rodzinne, które liczą zwykle co najwyżej kilka
osób, nie były dobrym środowiskiem do rozwoju współpracy?
\begin{center}
\begin{figure}[H]\label{poziomZmianPolski}
\begin{tabular}{cc}
\includegraphics[scale=0.6]{kooperacyjnoscGrupSym1.pdf}
&
\includegraphics[scale=0.6]{kooperacyjnoscGrupSym2.pdf}
\end{tabular}
\caption{Poziom kooperacji w grupach na zakończenie symulacji.}
\end{figure}
\end{center}

\subsubsection{Wnioski}

Wyniki opisanych powyżej symulacji pozwalają nam postawić następujące hipotezy:
\begin{enumerate}
\item \emph{Średni poziom kooperacji w najbardziej prawdopodobnym stanie
(względem rozkładu stacjonarnego) łańcucha Markowa opisującego dynamikę modelu
społeczeństwa polskiego wynosi $0,\!83$.}
\item \emph{Ewolucja grafu niezależna od ewolucji populacji ma znikomy wpływ na
dynamikę populacji.}
\item \emph{Kooperacja rozwija się lepiej w większych grupach społecznych.}
\end{enumerate}

Z uwagi na ogromną liczbę możliwych stanów w rozważanym łańcuchu
Markowa oraz stopień rozbudowania modelu, ograniczamy się tylko do
przeprowadzenia komputerowych symulacji.
Analiza teoretyczna jest zbyt skomplikowana.